package _dp_base;

/**
 * 5. 最长回文子串
 */
public class No5 {
    private String s;
    private String answer = "";

    /**
     * 0. 暴力
     */
    public String longestPalindrome0(String s) {
        this.s = s;
        for (int i = 0; i < s.length(); i++) {
            for (int j = i; j < s.length(); j++) {
                if (answer.length() < j + 1 - i && same(i, j)) {
                    answer = s.substring(i, j + 1);
                }
            }
        }
        return answer;
    }

    private String[][] cache;

    /**
     * 1. 递归
     */
    public String longestPalindrome1(String s) {
        this.s = s;
        int n = s.length();
        this.cache = new String[n][n + 1];

        return dfs(0, n);
    }

    private String dfs(int i, int j) {
        if (i >= j) return "";
        else if (cache[i][j] != null) return cache[i][j];
        if (j - i <= answer.length()) return answer;
        else if (same(i, j - 1)) return cache[i][j] = answer = s.substring(i, j);
        else {
            String l = dfs(i + 1, j);
            String r = dfs(i, j - 1);
            return cache[i][j] = l.length() > r.length() ? l : r;
        }
    }

    /**
     * 2. 迭代
     */
    public String longestPalindrome2(String s) {
        this.s = s;
        int n = s.length();
        String[][] f = new String[n][n + 1];
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i + 1; j < n + 1; j++) {
                if (j - i <= answer.length()) f[i][j] = answer;
                else if (same(i, j - 1)) f[i][j] = answer = s.substring(i, j);
                else {
                    String l = f[i + 1][j];
                    String r = f[i][j - 1];
                    f[i][j] = l.length() > r.length() ? l : r;
                }
            }
        }
        return f[0][n];
    }

    /**
     * 4. 空间优化
     */
    public String longestPalindrome4(String s) {
        this.s = s;
        int n = s.length();
        String[] f = new String[n + 1];
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i + 1; j < n + 1; j++) {
                if (j - i <= answer.length()) f[j] = answer;
                else if (same(i, j - 1)) f[j] = answer = s.substring(i, j);
                else {
                    String l = f[j];
                    String r = f[j - 1];
                    f[j] = l.length() > r.length() ? l : r;
                }
            }
        }
        return f[n];
    }

    /**
     * 判断当前子串是否为回文串
     */
    private boolean same(int l, int r) {
        while (l < r) {
            if (s.charAt(l) != s.charAt(r)) return false;
            l++;
            r--;
        }
        return true;
    }
}
